package com.david.learning.algorithm;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * To calculate the possible way to get 21 points by 4 cards
 * @author David Qi
 */
public class Card21 {
	public static final int[] CARDS = new int[] { 1, 2, 3, 4};
	public static final int CARD_NUMBER = 2;
	public static final int GOAL = 8;
	public static final iCalculator[] CALCULATORS = new iCalculator[] { new Addition(), new Multiplication(), new Subtraction()};

	public static void main(String[] args) {
		Set<Integer> cards = getSetbyArray(CARDS);
		System.out.println(calculateRound(0, 0, cards));
	}

	public static int calculateRound(int input, int round, Set<Integer> cards) {
		int sum = 0;
		if (round == CARD_NUMBER) {
			if (input == GOAL) {
				return 1;
			} else {
				return 0;
			}
		} else {
			round++;
			Iterator<Integer> it = cards.iterator();
			while(it.hasNext()){
				int i = it.next().intValue();
				it.remove();
				for (iCalculator c : CALCULATORS) {
					//Notice that we use getClone to get a new copy of cards.
					if(round == 1){
						sum += calculateRound(i, round, getClone(cards));
					}else{
						sum += calculateRound(c.calculate(input, i), round, getClone(cards));
					}
				}
			}
			return sum;
		}
	}

	public static Set<Integer> getClone(Set<Integer> goal) {
		Set<Integer> result = new HashSet<Integer>();
		for (Integer i : goal) {
			Integer element = new Integer(i.intValue());
			result.add(element);
		}
		return result;
	}

	public static Set<Integer> getSetbyArray(int[] input) {
		assert input != null;
		Set<Integer> result = new HashSet<Integer>();
		for (int i = 0; i < input.length; i++) {
			result.add(new Integer(input[i]));
		}
		return result;
	}
}

interface iCalculator {
	public int calculate(int first, int second);
}

class Addition implements iCalculator {
	public int calculate(int first, int second) {
		return first + second;
	}
	
	public String toString(){
		return " + ";
	}
}

class Multiplication implements iCalculator {
	public int calculate(int first, int second) {
		return first * second;
	}
	
	public String toString(){
		return " * ";
	}
}

class Subtraction implements iCalculator {
	public int calculate(int first, int second) {
		return first - second;
	}
	
	public String toString(){
		return " - ";
	}
}

class Division implements iCalculator {
	public int calculate(int first, int second) {
		double dFirst = Double.valueOf(first);
		double dSecond = Double.valueOf(second);
		double dResult = dFirst / dSecond;
		int result = (int) dResult;
		double dDifference = dResult - result;
		if (dDifference > 0) {
			throw new RuntimeException("Can't divide number: " + first + " and " + second);
		}
		return result;
	}
	
	public String toString(){
		return " / ";
	}
}